package arithmetic1.tree.huffmanTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
    赫夫曼树：树的带权路径长度最小
    构建赫夫曼树的步骤：
        1.将节点按权值从小到大排列，每次选出其中两个最小的节点，构成一颗树，树的根节点权值为两个节点权值的和
        2.将根节点放到原来的序列中，再次排序，重复以上过程，最后只有一个节点的时候就是一颗赫夫曼树
 */
public class HuffmanTree {
    private Node root;  //赫夫曼树的根节点

    public HuffmanTree() {
    }

    public HuffmanTree(Node root) {
        this.root = root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    //构建赫夫曼树
    public Node huffmanTree(int arr[]){
        List<Node> nodes=new ArrayList<>();
        //取出数组的所有数，封装成节点
        for(int value:arr){
            nodes.add(new Node(value));
        }
        while (nodes.size()>1){ //只要还有两个以上的节点，就一直重复
            //排序
            Collections.sort(nodes );
            //取出两个权值最小的节点
            Node node1=nodes.get(0);
            Node node2=nodes.get(1);
            //生成一个父节点
            Node parent=new Node(node1.value+node2.value);
            //将子节点添加到父节点下面
            parent.leftNode=node1;
            parent.rightNode=node2;
            //删除两个子节点
            nodes.remove(node1);
            nodes.remove(node2);
            //将父节点加入到集合
            nodes.add(parent);
        }
        //返回剩余的一个节点
        return nodes.get(0);
    }

    //前序遍历
    public void preOrder(Node root){
        if(root!=null){
            System.out.print(root.value+"\t");
            if(root.leftNode!=null){
                preOrder(root.leftNode);
            }
            if(root.rightNode!=null){
                preOrder(root.rightNode);
            }
        }else {
            System.out.println("该树是空树");
        }
    }
}
//节点
class Node implements Comparable<Node>{
    int value;
    Node leftNode;
    Node rightNode;

    public Node(int value) {
        this.value = value;
        leftNode=null;
        rightNode=null;
    }

    //节点从小到大排序
    @Override
    public int compareTo(Node o) {
        return this.value-o.value;
    }
}

class Test{
    public static void main(String[] args) {
        int arr[]={13,7,8,3,29,6,1};
        HuffmanTree tree=new HuffmanTree();
        Node root = tree.huffmanTree(arr);
        tree.setRoot(root);
        tree.preOrder(root);
    }
}

